Lowe, inventor of the U.S. Pat. No. 6,711,293 B1, used a modification of the k-d tree algorithm known as the Best-bin-first search method that can identify the nearest neighbors with high probability using only a limited amount of computation.
US 2010/0067745 discloses a method for object clustering and identification in video. In particular, it concerns the identification of facial images. The method uses clusters of video objects which are likely associated with the same person. A new image is deemed to belong to an existing cluster if the distance to the cluster is smaller than a first predetermined threshold distance. The new image becomes part of the cluster if the distance is larger than a second threshold distance (smaller than the first threshold distance).
Ye, L., et al., “Autocannibalistic and Anyspace Indexing Algorithms with Applications to Sensor Data Mining”, Dept. of Computer Science & Eng., University of California, Riverside, USA, 85-96, provides an altered Orchard algorithm. Here, speed is sacrificed in order to reduce memory requirement. It is a design choice how much speed is sacrificed to save memory. However, the algorithm in any case requires a minimum of space. In Orchards algorithm, for each item in a dataset, a sorted list of its neighbors is calculated. This requires large amounts of memory for large dataset. In the altered Orchard algorithm, rows for items which are close to each other are deleted to save space. Thus, the search algorithm sacrifices speed for memory space. Ye et al. further suggests dynamic memory allocation for optimizing the algorithm.
Vidal Ruiz, E., “An algorithm for finding nearest neighbours in (approximately) constant average time”, Pattern Recognition Letters 4 (1986), 145-157, relates to an algorithm for finding the Nearest Neighbour of a given sample in approximately constant average time complexity (i.e. independent of the data set size).